package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         239,
		Discription: "滑动窗口最大值",
		Level:       2,
		Labels: map[string]int{
			"单调队列": 1,
			"滑动窗口": 1,
		},
	})
}

//维护一个单调递减的队列，q[0]是滑动窗口内的最大值
func MaxSlidingWindow(nums []int, k int) []int {
	q := []int{nums[0]}
	for i := 1; i < k; i++ {
		for len(q) > 0 && nums[i] > q[len(q)-1] {
			q = q[:len(q)-1]
		}
		q = append(q, nums[i])
	}
	res := []int{q[0]}

	for i := k; i < len(nums); i++ {
		removedVal := nums[i-k]
		if removedVal == q[0] {
			q = q[1:]
		}

		for len(q) > 0 && nums[i] > q[len(q)-1] {
			q = q[:len(q)-1]
		}
		q = append(q, nums[i])
		res = append(res, q[0])
	}

	return res
}

/* func maxSlidingWindow(nums []int, k int) []int {
	q := make([]int, 0)
	for i := 0; i < k; i++ {
		if len(q) == 0 || nums[i] <= q[len(q)-1] {
			q = append(q, nums[i])
			continue
		}

		j := len(q) - 1
		for ; j >= 0; j-- {
			if nums[i] <= q[j] {
				break
			}
		}
		q = q[:j+1]
		q = append(q, nums[i])
	}

	res := []int{q[0]}
	for i := k; i < len(nums); i++ {
		if nums[i-k] == q[0] {
			q = q[1:]
		}

		if len(q) == 0 || nums[i] <= q[len(q)-1] {
			q = append(q, nums[i])
		} else {
			j := len(q) - 1
			for ; j >= 0; j-- {
				if nums[i] <= q[j] {
					break
				}
			}
			q = q[:j+1]
			q = append(q, nums[i])
		}

		res = append(res, q[0])
	}

	return res
} */
